package com.peng.sort.merge;

import com.peng.utils.TestUtils;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/count-of-range-sum/
 * 给定一个数组arr，两个整数lower和upper，
 * 返回arr中有多少个子数组的累加和在[lower,upper]范围上
 * 例如数组：[5,3,2,7,4,8]，求在[8,12]范围上的子数组有哪些？
 * 以每个数结尾尝试，符合的：
 * 5结尾： 不存在
 * 3结尾： [5,3]
 * 2结尾： [5,3,2]
 * 7结尾：[2,7],[3,2,7]
 * 4结尾：[7,4]
 * 8结尾：[8]，[4,8]
 * <p>
 * 因此符合的一共有6个子数组
 */
public class Test04_SubArrSumInRangeCount {
    public static void main(String[] args) {

//        int[] arr = {-5,12,74};
//        int subArrSumInRangeCount = getSubArrSumInRangeCount(arr, 5, 12);
//        int subArrSumInRangeCountEasy = getSubArrSumInRangeCountEasy(arr, 5, 12);
//        System.out.println(subArrSumInRangeCount);
//        System.out.println(subArrSumInRangeCountEasy);
////
//        if (1 == 1) return;
        int testTime = 500000;
        int maxSize = 3;
        int maxValue = 100;
        int lower = 5;
        int upper = 12;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = TestUtils.generateRandomArray(maxSize, maxValue);
            int[] arr2 = TestUtils.copyArray(arr1);
            try {
                if (getSubArrSumInRangeCount(arr1, lower, upper) != getSubArrSumInRangeCountEasy(arr2, lower, upper)) {
                    succeed = false;
                    TestUtils.printArray(arr1);
                    TestUtils.printArray(arr2);
                    break;
                }
            } catch (Exception e) {
                System.out.println(Arrays.toString(arr1));
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

    }

    //对数器
    public static int getSubArrSumInRangeCountEasy(int[] arr, int lower, int upper) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int[] sumArr = new int[arr.length];
        sumArr[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sumArr[i] = sumArr[i - 1] + arr[i];
        }
        int res = 0;

        for (int i = 0; i < sumArr.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (i == j) {
                    if (sumArr[i] >= lower && sumArr[j] <= upper) {
                        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, i + 1)));
                        res++;
                    }
                    continue;
                }
                if (sumArr[i] - sumArr[j] >= lower && sumArr[i] - sumArr[j] <= upper) {
                    System.out.println(Arrays.toString(Arrays.copyOfRange(arr, j + 1, i + 1)));
                    res++;
                }
            }
        }

        return res;
    }

    public static int getSubArrSumInRangeCount(int[] arr, int lower, int upper) {
        if (arr == null || arr.length < 1) {
            return 0;
        }

        int[] sumArr = new int[arr.length];
        sumArr[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sumArr[i] = sumArr[i - 1] + arr[i];
        }

        return process(sumArr, 0, sumArr.length - 1, lower, upper);
    }

    private static int process(int[] arr, int L, int R, int lower, int upper) {
        if (L == R) {
            return arr[L] >= lower && arr[L] <= upper ? 1 : 0;
        }
        int mid = L + ((R - L) >> 1);

        return process(arr, L, mid, lower, upper)
                + process(arr, mid + 1, R, lower, upper)
                + merge(arr, L, mid, R, lower, upper);
    }

    private static int merge(int[] sumArr, int L, int mid, int R, int lower, int upper) {
        int p1 = L;
        int p2 = mid + 1;
        int[] help = new int[R - L + 1];
        int i = 0;

        int res = 0;

        int windowL = L;
        int windowR = L;
        for (int m = mid + 1; m <= R; m++) {
            int lowerRange = sumArr[m] - upper;
            int upperRange = sumArr[m] - lower;

            while (windowL <= mid && sumArr[windowL] < lowerRange) {
                windowL++;
            }

            while (windowR <= mid && sumArr[windowR] <= upperRange) {
                windowR++;
            }
            res += windowR - windowL;


        }


        while (p1 <= mid && p2 <= R) {
            if (sumArr[p1] < sumArr[p2]) {
                help[i++] = sumArr[p1++];
            } else {
                help[i++] = sumArr[p2++];
            }
        }

        while (p1 <= mid) {
            help[i++] = sumArr[p1++];
        }
        while (p2 <= R) {
            help[i++] = sumArr[p2++];
        }


        for (int m = 0; m < help.length; m++) {
            sumArr[L + m] = help[m];
        }

        return res;
    }
}
